The present invention relates to enhanced turbo product codes (eTPCs), in general, and in particular, a method for encoding hyper-product codes by diagonal encoding and an apparatus for doing the same.
A product code is a concatenation of two or more block codes C1 and C2, each having parameters (n1, k1, d1) and (n2, k2, d2) where n is the codeword length, k is the number of information bits and d is the minimum Hamming distance. The product code P=C1×C2 is obtained by placing k1×k2 information bits in an array of k1 rows and k2 columns. Following, the k1 rows are coded using code C1 and n2 columns are coded using C2. Thus, the resulting product code is (n1×n2, k1×k2, d1×d2). Under such construction, all rows of the matrix P are codewords of C1 and all columns of matrix P are codewords of C2. Product codes can be two dimensional or multi dimensional. However, when the dimensions of the product become higher, codes with larger euclidean distances (dmin) are more easily obtained, but at a cost of significant increase in block size.
Turbo Product Codes (TPCs) is a class of codes that offer performance closer to Shannon's limit than traditional concatenated codes. TPCs are the iterative soft decision decoding of a product code. TPCs are a class of codes with a wide range of flexibility in terms of performance, complexity and code rate. This flexibility allows TPCs to be used in a wide range of applications.
An enhanced turbo product code is a code built with a TPC base. The base code can be any number of dimensions and may contain parity and/or extended Hamming constituent codes. When all axes of the code contain parity only constituent codes, the codes is a “hyper product code”. Enhanced turbo product codes (eTPCs) include the N dimensional product of extending Hamming codes and simple parity codes followed by an additional parity calculation which is computed along a “hyper diagonal”, where the product code has one or more dimensions. ETPCs admit a low-complexity implementation and can be iteratively decoded with a soft-in soft-out (SISO) algorithm.
To move from the base TPC to an eTPC , the bits in the base code are shuffled or interleaved according to a predetermined pattern. The parity is then computed over the new shuffled array. The parity is computed such that one additional row of bits is added to a 2-D TPC, or one additional plane is added to a 3-D TPC. This can be generalized to more dimensions since a n−1 dimensional structure of parity bits is added to the code where “n” is the dimension of the base code.
In addition to bit error rate performance improvement, eTPCs also have value in terms of flexibility. System designers generally required a variety of block sizes and code rates when developing a system employing error correction. The ability to use the entire set of eTPCs (including turbo product codes, enhanced turbo product codes and any combination thereof) give great flexibility in choosing an exact code for a given system.
The code rate and Best Error Rate (BER) performance of TPCs is dependent on the systematic, constituent block code codewords and the number of axes in the product code. The set of eTPCs shown below include codes of 2 or more dimensions, where the base code on each axis can include extended Hamming codes and/or parity codes or other equivalents. The table below shows the set of 2-D and 3-D eTPC code configurations:
CodeEstimated MinimumConfigurationsDistancePP4PP+~6HP8HP+~10HH16PPP8PPP+~12HPP16HPP+~20HH+~20HHP32HHP+~40HHH64HHH+~80
In the table above, an ‘H’ represents an extended Hamming code axis, a ‘P’ represents a parity only axis, and a ‘+’ indicates a enhanced turbo product code containing the additional hyper-diagonal axis. For example, a HP+ code contains an extended Hamming code in the X axis, a parity only code in the Y axis and an additional hyper-diagonal axis. The minimum distance for codes containing the hyper-diagonal axis depends on the length of the code axis and must be found by computer analysis. The table shows an estimate of the minimum distance for these codes in the right column. It is shown in the above table that the minimum distance for the codes increases as more axes of the code are coded. In addition, the minimum distance of the codes also increase as a hyper-diagonal axis is added to the code. In turn, the code rate in encoding the code decreases, which increases the performance of the encoder.
The diagonal parity bits or hyper-diagonal is obtained by adding bits diagonally along the block by using the following equation:
                              P          i                =                              ∑                          k              =              0                                                      m                1                            -              1                                ⁢                      B                                          i                +                k                            ,              k                                                          (        1        )            where Bi,j is the (i,j)th product code bit. The diagonal parity bits can be generated by right “rotating” the ith row of the original product by i+1 bits, then adding each column to get the diagonal parity bits. Likewise, diagonal parity bits can also be generated by left rotating the ith row of the original product code by i−1 bits, then adding each column to get the diagonal parity bits.
The addition of the diagonal parity bits increases the minimum Euclidean distance, dmin, of the code. The diagonal axis is often referred to as a hyper axis even when it is used with Hamming codes in the various axes. The increased minimum distance will result in a lower error floor of the code. Further, the addition of a hyper axis can improve the performance of the code before the bound.
A prior art method of encoding is to place the data in a kx×ky (kx, ky) array of bits. FIG. 1 generally illustrates the method of encoding in accordance with the present invention. The x-axis of the code is encoded by an x-axis encoder 10 which encodes each row resulting in a block of data having ky rows of nx bits per row (nx, ky). This block of data is input to a Y axis encoder 11 that encodes each column by adding data to the Y axis, resulting in a (nx, ny) block output. The last step includes a hyper axis encoder 12 which adds the diagonal parity bits to the code. Then, a parity only encode is applied to all columns of the block. The result adds one row to the block, resulting in a (nx, ny+l ) output block.
The prior art method of encoding has several disadvantages. One full encoded 2-D block having a code (nx, ny) of storage is required in the encoder to hold both the data array and the error correction coding (ECC) bits. In addition, the encoder has a one block latency. Latency is defined as the time between the first bit of a block of data is input into the encoder and the last bit of the same block is output from the encoder. The prior art encoder have a high latency, because the encoder cannot output the data array until it finishes encoding both rows and columns. To complete this encoding process, the encoder must receive the entire data array. Therefore, the first data bit of the block cannot be output until the last data bit of the same block is input making the latency one full block. Many communications type systems cannot handle high latency because of the Quality of Service constraints placed on the system. For example, a ½ second delay on a telephone line is undesirable, because the delay inhibits communication between the transmitting and receiving ends.
What is needed is an efficient hardware implementation and method thereof of iterative encoding for eTPCs with a hyper diagonal parity array added, where the eTPC includes systematic bloc code codewords such as extended Hamming codes, parity codes as well as other codes. Using eTPCs with iterative diagonal encoding and decoding is advantageous, because such eTPC have an error floor of three to five orders of magnitude lower than the corresponding turbo-product codes.
What is also needed is an encoder than can encode the data ‘on the fly’ without storing the entire block in storage. Such an encoder should have very low latency because it would not store the data bits, but only store the error correction bits. The data bits would be transmitted immediately over the channel, making the latency near zero. In addition, such an encoder would have smaller storage requirements, because the encoder is not storing the data array itself.